﻿//#define _CRT_SECURE_NO_WARNINGS 1
//小易是一个数论爱好者，并且对于一个数的奇数约数十分感兴趣。
//一天小易遇到这样一个问题： 定义函数f(x)为x最大的奇数约数，
//x为正整数。 例如 : f(44) = 11.
//现在给出一个N，需要求出 f(1) + f(2) + f(3).......f(N)
//例如： N = 7
//f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 1 + 3 + 1 + 5 + 3 + 7 = 21
//小易计算这个问题遇到了困难，需要你来设计一个算法帮助他。
//#include <stdio.h>
//int main()
//{
//	long long n = 0, i = 0;
//	long long count = 0;
//	scanf("%lld", &n);
//	for (i = n; i>0; i /= 2)
//	{
//		count += ((i + 1) / 2)*((i + 1) / 2);
//	}
//	printf("%lld", count);
//	return 0;
//}  
//
//
//
//
//
//
//
//
//如果一个01串任意两个相邻位置的字符都是不一样的,
//我们就叫这个01串为交错01串。例如: "1", "10101", "0101010"都是交错01串。
//小易现在有一个01串s, 小易想找出一个最长的连续子串,
//并且这个子串是一个交错01串。小易需要你帮帮忙求出最长的这样的子串的长度是多少
//#include <stdio.h>
//#include <string.h>
//int main()
//{
//	char arr[50];
//	scanf("%s", arr);
//	int len = strlen(arr);
//	int count = 1;
//	int i = 0;
//	int max = 1;
//	for (i = 0; i<len - 1; i++)
//	{
//		if (arr[i] != arr[i + 1])
//		{
//			count++;
//		}
//		else
//		{
//			count = 1;
//		}
//		if (max<count)
//		{
//			max = count;
//		}
//	}
//	printf("%d", max);
//
//	return 0;
//}
//
//
//
//
//
//
//
//小葱去里约看奥运会，早上从酒店出来后决定坐公交车吗，
//但是没有直达的路线，只能通过多次换乘公交来达到目的地，
//现在希望你可以编写一个程序帮助小葱算数到达目的地所需的最少时间
//#include　<stdio.h>
//void dfs(int cu, int end, int n, int *pa, int *num, unsigned int w, unsigned int *min)
//{
//	int i = 0;
//	for (i = 0; i<num[cu]; i++)
//	{
//		w += pa[cu * 2 * n + 2 * i + 1];
//		if (pa[cu * 2 * n + 2 * i]<end)
//		{
//			dfs(pa[cu * 2 * n + 2 * i], end, n, pa, num, w, min);
//		}
//		else if (pa[cu * 2 * n + 2 * i] == end)
//		{
//			if (w<*min)
//			{
//				*min = w;
//			}
//		}
//		w -= pa[cu * 2 * n + 2 * i + 1];
//	}
//}
//int main()
//{
//	int end;
//	int n = 0;
//	scanf("%d %d", &end, &n);
//	int a[n][3];
//	int i = 0;
//	for (i = 0; i<n; i++)
//	{
//		scanf("%d %d %d", *(a + i), *(a + i) + 1, *(a + i) + 2);
//	}
//	int pa[end*(2 * n)];
//	int num[end];
//	memset(num, 0, end*sizeof(int));
//	int j = 0;
//	for (i = 0; i<end; i++)
//	{
//		for (j = 0; j<n; j++)
//		{
//			if (a[j][0] == i)
//			{
//				pa[i * 2 * n + num[i] * 2] = a[j][1];
//				pa[i * 2 * n + num[i] * 2 + 1] = a[j][2];
//				num[i]++;
//			}
//		}
//	}
//	unsigned int min = 0xfffffff;
//	int w = 0;
//	dfs(0, end, n, pa, num, w, &min);
//	if (min<0xfffffff)
//	{
//		printf("%d\n", min);
//	}
//	else
//	{
//		printf("-1\n");
//	}
//	return 0;
//}
//
//
//
//
//
//
//
//第一行包含一个数字𝑛，表示排列的长度。2 ≤ 𝑛 ≤ 105
//第二行包含𝑛个数字构成一个𝑛排列。
//#include <stdio.h>
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int i = 0;
//	int p = 0;
//	int tmp = 0;
//	int a[n];
//	for (i = 0; i<n; i++)
//	{
//		scanf("%d", &a[i]);
//	}
//	for (i = 0; i<n; i++)
//	{
//		if (a[i] != i + 1)
//		{
//			p = i;
//			break;
//		}
//	}
//	if (i == n)
//	{
//		tmp = a[n - 1];
//		a[n - 1] = a[n - 2];
//		a[n - 2] = tmp;
//	}
//	else
//	{
//		for (i = 0; i<n; i++)
//		{
//			if (a[i] == p + 1)
//			{
//				tmp = a[i];
//				a[i] = a[p];
//				a[p] = tmp;
//				break;
//			}
//		}
//	}
//	for (i = 0; i<n; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//	return 0;
//}







//有一个长为n的数组A，求满足0≤a≤b<n的A[b] - A[a]的最大值。
//给定数组A及它的大小n，请返回最大差值。
//class LongestDistance {
//public:
//	int getDis(vector<int> A, int n) {
//		// write code here
//		if (n == 0)
//		{
//			return 0;
//		}
//		int min_v = A[0];
//		int sum = 0;
//		for (int i = 0; i<n; i++)
//		{
//			min_v = min(min_v, A[i]);
//			sum = max(sum, A[i] - min_v);
//		}
//		return sum;
//	}
//};






//#include <stdio.h>
//#include <string.h>
//void add(char *p, char* q)
//{
//	while (p <= q)
//	{
//		char tmp = 0;
//		tmp = *p;
//		*p = *q;
//		*q = tmp;
//		p++;
//		q--;
//	}
//}
//int main()
//{
//	char arr[] = "abc def bejing";
//	char* i = arr;
//	char *sz = i;
//	int len = strlen(arr);
//	while (*i)
//	{
//		if (*i != ' ')
//		{
//			i++;
//		}
//		else if (*i == ' ')
//		{
//			add(sz,i-1);
//			sz = i + 1;
//			i++;
//		}
//	}
//	add(sz, i-1);
//	sz = 0;
//	add(arr, arr + len - 1);
//	printf("%s\n", arr);
//	return 0;
//}







//牛客最近来了一个新员工Fish，
//每天早晨总是会拿着一本英文杂志，
//写些句子在本子上。
//同事Cat对Fish写的内容颇感兴趣，
//有一天他向Fish借来翻看，但却读不懂它的意思。
//例如，“nowcoder.a am I”。
//后来才意识到，这家伙原来把句子单词的顺序翻转了，
//正确的句子应该是“I am a nowcoder.”。
//Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
//class Solution {
//public:
//	string ReverseSentence(string str) {
//		string tmp = "";
//		string ans = "";
//		int len = str.length();
//		for (int i = len - 1; i >= 0; i--)
//		{
//			if (str[i] != ' ')
//			{
//				tmp = str[i] + tmp;
//			}
//			else
//			{
//				ans += tmp + ' ';
//				tmp = "";
//			}
//		}
//		if (tmp.length() != 0)
//		{
//			ans += tmp;
//		}
//		return ans;
//	}
//};






///**把只包含质因子2、3和5的数称作丑数（Ugly Number）。
//例如6、8都是丑数，但14不是，因为它包含质因子7。 
//习惯上我们把1当做是第一个丑数。
//求按从小到大的顺序的第N个丑数。
//*
//* @param index int整型
//* @return int整型
//*/
//int min(int a, int b, int c)
//{
//	if (a <= b&&a <= c)
//	{
//		return a;
//	}
//	else if (b <= a&&b <= c)
//	{
//		return b;
//	}
//	else if (c <= a&&c <= b)
//	{
//		return c;
//	}
//	else
//	{
//		return 0;
//	}
//}
//int GetUglyNumber_Solution(int index) {
//	// write code here
//	if (index <= 0)
//	{
//		return 0;
//	}
//	int a[1000000];
//	a[0] = 1;
//	int p2 = 0, p3 = 0, p5 = 0;
//	int i = 0;
//	for (i = 1; i <= index; i++)
//	{
//		a[i] = min(a[p2] * 2, a[p3] * 3, a[p5] * 5);
//		if (a[i] % 2 == 0)
//		{
//			p2++;
//		}
//		if (a[i] % 3 == 0)
//		{
//			p3++;
//		}
//		if (a[i] % 5 == 0)
//		{
//			p5++;
//		}
//	}
//	return a[index - 1];
//}
//
//
//
//
//
//
//
//在一个字符串(0 <= 字符串长度 <= 10000，全部由字母组成)
//中找到第一个只出现一次的字符, 并返回它的位置, 
//如果没有则返回 - 1（需要区分大小写）.（从0开始计数）
//class Solution {
//public:
//	int FirstNotRepeatingChar(string str) {
//		int i = 0;
//		int j = 0;
//		int n = str.size();
//		if (n == 0)
//		{
//			return -1;
//		}
//		if (n == 1)
//		{
//			return 0;
//		}
//		for (i = 0; i<n; i++)
//		{
//			int flag = 0;
//			for (j = 0; j<n; j++)
//			{
//				if (i != j&&str[i] == str[j])
//				{
//					flag = 1;
//					break;
//				}
//			}
//			if (flag == 0)
//			{
//				return i;
//			}
//		}
//		return -1;
//	}
//};
//






//一只青蛙一次可以跳上1级台阶，
//也可以跳上2级……它也可以跳上n级。
//求该青蛙跳上一个n级的台阶总共有多少种跳法。
//class Solution {
//public:
//	int jumpFloorII(int number) {
//		if (number == 0 || number == 1)
//		{
//			return 1;
//		}
//		if (number == 2)
//		{
//			return 2;
//		}
//		int sum = 2;
//		for (int i = 3; i <= number; i++)
//		{
//			sum *= 2;
//		}
//		return sum;
//	}
//};